class Node {
    private Object item;
    private Node left;
    private Node right;

    public Node(Object item) {
	this(item, null, null);
    }
    public Node(Object item, Node left, Node right) {
	this.item = item;
	this.left = left;
	this.right = right;
    }
    private void visit() {
	System.out.print(item + " ");
    }
    public void preorder() {
	visit();
	if (left != null)
	    left.preorder();
	if (right != null)
	    right.preorder();
    }
    public void postorder() {
	if (left != null)
	    left.postorder();
	if (right != null)
	    right.postorder();
	visit();
    }
    public void inorder() {
	if (left != null)
	    left.inorder();
	visit();
	if (right != null)
	    right.inorder();
    }
    public int size() {
	int size = 1;
	if (left != null)
	    size += left.size();
	if (right != null)
	    size += right.size();
	return size;
    }
    public int height() {
	int height = -1;
	if (left != null)
	    if (left.height() > height)
		height = left.height();
	if (right != null)
	    if (right.height() > height)
		height = right.height();
	return height + 1;
    }
    public Node duplicate() {
	Node n = new Node(item);
	if (left != null)
	    n.left = left.duplicate();
	if (right != null)
	    n.right = right.duplicate();
	return n;
    }

}

class BinaryTree {
    public static Node makeTree() {
	return
	    new Node("*",
		     new Node("+", 
			      new Node("*",
				       new Node("2"),
				       new Node("4")
				       ),
			      new Node("/",
				       new Node("8"),
				       new Node("4")
				       )
			      ),
		     new Node("-",
			      new Node("2"),
			      new Node("4")
			      )
		     );
    }

    public static void main(String[] args) {
	Node tree = makeTree();
	System.out.println("PREorder");
	tree.preorder();
	System.out.println();
	System.out.println("POSTorder");
	tree.postorder();
	System.out.println();
	System.out.println("INorder");
	tree.inorder();
	System.out.println();
	System.out.println("size " + tree.size());
	System.out.println("height " + tree.height());
	Node tree2 = tree.duplicate();
	System.out.println("INorder");
	tree2.inorder();
	System.out.println();
    }
}